1. Field of the Invention
The present invention relates to the field of computer systems. More specifically, the present invention relates to register allocations performed by compilers of these computer systems.
2. Background
In U.S. Pat. No. 4,571,678, Chaitin described a method for allocating registers based on graph coloring. An interference graph is used to represent the conflicts between register candidates. The register candidates are represented as nodes. Two nodes are connected with an edge if the two register candidates are both live at some point in the program. If the nodes in the interference graph can be colored in k or fewer colors, where any pair of nodes connected by an edge receive different colors, and k is the number of registers available for allocation on the target machine, then the coloring corresponds to an allocation. If k-coloring cannot be achieved, then code are introduced to spill one or more register candidates, and restore them subsequently before they are used. After spilling the node, it is removed from the interference graph. The coloring process is then repeated with the new interference graph. The process is repeated until a k-coloring is found.
Thus, under Chaitin's method, a register may be allocated to two register candidates even though they are both live in the same basic block of a program, as long as they are not both live at some point in that same basic block. However, under Chaitin, a register candidate is either allocated a register or spilled. Once a register candidate is spilled, it is spilled for all basic blocks in which the register candidate is live.
In an ACM article entitled The Priority-Based Coloring Approach to Register Allocation, ACM Transactions on Programming Languages and Systems, Vol. 12, No. 4, October 1990, pp 501-536, Chow and Hennessy described a different method for performing global register allocations, (local register allocations are performed by the code generator). Under Chow and Hennessy, the process of coloring is applied first to constrained live ranges, and then to unconstrained live ranges. Unconstrained live ranges have a number of neighboring live ranges in the interference graph less than the original number of registers available for allocation. Constrained live ranges are live ranges that are not unconstrained. A live range is an isolated and contiguous group of nodes in the control flow graph in which a program data value is alive. A node in the control flow graph is a basic block of the program.
Thus, under Chow and Hennessy's method, a live range may be allocated a register in one basic block, but spilled in another basic block. However, a register may not be allocated to two live ranges in a basic block even though they are not beth live at some point in that same basic block.
Thus, it is desirable if a register can be allocated to two register candidates that are live in the same basic block as long as they are not live at some point in the basic block as in Chaitin's method, and at the same time, a register candidate can be spilled in one basic block and allocated a register in another basic block as in Chow and Hennessy's method. As will be disclosed, the improved method and apparatus of the present invention for allocating registers substantially achieves the above described desired results.